% overview.tex

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.80\textwidth}{figs/welcome-again}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    {\large the ``father of the analysis of algorithms''}
  \end{center}

  \begin{columns}
    \column{0.50\textwidth}
      \fig{width = 0.80\textwidth}{figs/knuth-chair}
    \column{0.50\textwidth}
      \fig{width = 0.80\textwidth}{figs/taocp-box}
  \end{columns}

  \pause
  \vspace{0.30cm}
  \begin{center}
    \teal{Donald E. Knuth (1938 $\sim$)} \\[6pt]
    \teal{Turing Award, 1974}
  \end{center}

  % \pause
  % \vspace{0.30cm}
  % \begin{quote}
  %   \centering
  %   ``For his major contributions to the analysis of algorithms
  %     and \red{the design of programming languages},
  %     and in particular for his contributions to ``The Art of Computer Programming''
  %     through his well-known books in a continuous series by this title.''

  %   \hfill --- Turing Award, 1974
  % \end{quote}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    ``Selected Papers on Computer Languages''

    \fig{width = 0.30\textwidth}{figs/selected-papers-lang}

    \red{{\bf LR Parser} \qquad {\bf Attribute Grammar} \qquad ALGOL 58 Compiler}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \fig{width = 0.40\textwidth}{figs/video}

    \vspace{0.50cm}
    \href{https://youtu.be/QeiuVNDQg4k}{``I got a job at the end of my senior year 
    \\ to write a compiler for Burroughs''}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    $55K = 50K + 5K$ (\red{\bf 子过程})

    \pause
    \vspace{0.80cm}
    \fig{width = 0.50\textwidth}{figs/20201225}
    进展顺利的话, 各位在\blue{\bf 圣诞节}就能用上自己的编译器了

    \pause
    \vspace{1.00cm}
    \red{\bf 免责声明:} 关于能否顺利找到女朋友/男朋友, 本课程无法提供任何保证
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \[
      \text{``高级''语言 $\implies$ \gray{(通常)} ``低级''语言 (如, 汇编语言)}
    \]
    汇编语言经过{\bf 汇编器}生成机器语言

    \vspace{0.30cm}
    \fig{width = 0.40\textwidth}{figs/compiler-blackbox}

    \pause
    \begin{columns}
      \column{0.50\textwidth}
        \fig{width = 0.60\textwidth}{figs/gopherjs-logo}
      \column{0.50\textwidth}
        \fig{width = 0.95\textwidth}{figs/gopherjs}
    \end{columns}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{$Q:$ 机器语言是如何跑起来的?}

    \pause
    \vspace{0.60cm}
    \red{\bf 作业:} \teal{\url{https://www.bilibili.com/video/BV1EW411u7th}}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    {\large 两个月的``编译器设计原理''之旅}

    \vspace{0.30cm}
    \begin{columns}
      \column{0.50\textwidth}
        \fig{width = 0.85\textwidth}{figs/compiler-blackbox}
      \column{0.50\textwidth}
        \fig{width = 0.60\textwidth}{figs/keep-calm-open-box}
    \end{columns}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[fragile]{}
%   \begin{columns}
%     \column{0.60\textwidth}
%       \fig{width = 0.80\textwidth}{figs/lang-processing-system}
%     \column{0.40\textwidth}
%       \fig{width = 0.80\textwidth}{figs/gcc-v}
%   \end{columns}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    IR: Intermediate Representation (中间表示)
    \vspace{0.50cm}

    \fig{width = 0.80\textwidth}{figs/front-back}

    \vspace{0.50cm}
    前端 \red{\bf (分析阶段)}: 分析源语言程序, 收集所有必要的信息 \\[8pt]
    后端 \red{\bf (综合阶段)}: 利用收集到的信息, 生成目标语言程序
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \fig{width = 0.80\textwidth}{figs/optimizer}

    \vspace{0.50cm}
    机器无关的中间表示优化
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{columns}
    \column{0.50\textwidth}
      \begin{center}
        编译器前端: 分析阶段
        \fig{width = 0.95\textwidth}{figs/front-end}

        \teal{前四次必做实验}
      \end{center}
    \column{0.50\textwidth}
      \begin{center}
        编译器后端: 综合阶段
        \fig{width = 0.50\textwidth}{figs/back-end}

        \teal{第五次选做实验}
      \end{center}
  \end{columns}

  \pause
  \fig{width = 0.50\textwidth}{figs/assignment}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    作为一名\red{\bf 程序员}, 你看到了什么?

    \vspace{0.10cm}
    \fig{width = 0.50\textwidth}{figs/assignment}

    \vspace{0.20cm}
    \begin{columns}
      \column{0.10\textwidth}
      \column{0.80\textwidth}
        \begin{description}
          \setlength{\itemsep}{12pt}
          \pause
          \item[词法:] 标识符、数字、运算符
          \pause
          \item[语法:] 包含算术运算的赋值语句
          \pause 
          \item[语义:] \texttt{position, initial, rate} 是数值类型
          \pause
          \item[物理定律:] $\text{当前位置 } = \text{ 初始位置 } + \text{ 速度 } \times \text{ 时间}$
        \end{description}
      \column{0.10\textwidth}
    \end{columns}

    \pause
    \vspace{1.00cm}
    但是, 作为\blue{\bf 编译器}, 它仅仅看到了一个\blue{\bf 字符串}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 词法分析器 (Lexer/Scanner):} 将{\bf 字符}流转化为{\bf 词法单元} (token) 流。

    \[
      \boxed{\text{token}: \langle \text{token-class}, \text{attribute-value} \rangle}
    \]

    \fig{width = 0.50\textwidth}{figs/assignment}

    \begin{align*}
      \langle \id, \red{1} \rangle \quad 
      \langle \ws \rangle \quad
      \langle \assign \rangle \quad
      \langle \ws \rangle \quad
      \langle \id, \red{2} \rangle \quad
      \langle \ws \rangle \quad \\
      \langle + \rangle \quad
      \langle \ws \rangle \quad
      \langle \id, \red{3} \rangle \quad
      \langle \ws \rangle \quad
      \langle \ast \rangle \quad
      \langle \ws \rangle \quad
      \langle \num, \red{4} \rangle
    \end{align*}
    (此处, $1, 2, 3, 4$ 是指向\red{\bf 符号表}的指针)
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 语法分析器 (Parser):} 构建{\bf 词法单元}之间的语法结构, 生成\blue{\bf 语法树}

    \vspace{0.80cm}
    \fig{width = 0.50\textwidth}{figs/assignment}
    \fig{width = 0.50\textwidth}{figs/syntax-tree}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 语义分析器:} 语义检查, 如{\bf 类型检查}、{\bf ``先声明后使用''约束检查}

    \vspace{0.80cm}
    % \fig{width = 0.50\textwidth}{figs/assignment}
    \fig{width = 0.50\textwidth}{figs/semantic-analysis}

    \vspace{0.30cm}
    通过语法树上的遍历来完成
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 中间代码生成器:} 生成中间代码, 如 {\bf ``三地址代码''}

    \vspace{0.80cm}
    % \fig{width = 0.50\textwidth}{figs/assignment}
    \fig{width = 0.50\textwidth}{figs/ICG}

    \vspace{0.30cm}
    中间代码类似目标代码, 但不含有机器相关信息 (如寄存器、指令格式)
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 中间代码优化器}

    \vspace{0.80cm}
    % \fig{width = 0.50\textwidth}{figs/assignment}
    \fig{width = 0.50\textwidth}{figs/CO}

    \vspace{0.30cm}
    编译时计算、消除冗余临时变量
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 代码生成器:} 生成目标代码, 主要任务包括{\bf 指令选择、寄存器分配}

    \vspace{0.80cm}
    % \fig{width = 0.50\textwidth}{figs/assignment}
    \fig{width = 0.50\textwidth}{figs/CG}
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 符号表:} 收集并管理{\bf 变量名/函数名}相关的信息
  \end{center}

  \begin{columns}
    \column{0.50\textwidth}
      \begin{center}
        \blue{\bf 变量名:} \\[3pt]
        类型、寄存器、内存地址、行号

        \vspace{0.50cm}
        \blue{\bf 函数名:} \\[3pt]
        参数个数、参数类型、返回值类型
      \end{center}
    \column{0.50\textwidth}
      \fig{width = 0.80\textwidth}{figs/symbol-table}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \fig{width = 0.85\textwidth}{figs/st-api}

  \vspace{0.50cm}
  \begin{center}
    红黑树 (RB-Tree)、哈希表 (Hashtable)
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    为了方便表达\red{\bf 嵌套结构与作用域}, 可能需要维护多个符号表
  \end{center}

  \fig{width = 0.50\textwidth}{figs/nested-symbol-tables}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}
  \begin{center}
    \red{\bf 时间苦短, 来不及优化}
  \end{center}

  \begin{columns}
    \column{0.50\textwidth}
      \fig{width = 0.95\textwidth}{figs/front-end}
    \column{0.50\textwidth}
       \fig{width = 0.50\textwidth}{figs/back-end}
  \end{columns}

  \vspace{0.30cm}
  \begin{center}
    但是, 在设计实际生产环境中的编译器时, {\bf 优化}通常占用了大多数时间
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%